{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Latest Group of Size M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLatestStep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找大小为 M 的最新分组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>arr</code> ，该数组表示一个从 <code>1</code> 到 <code>n</code> 的数字排列。有一个长度为 <code>n</code> 的二进制字符串，该字符串上的所有位最初都设置为 <code>0</code> 。</p>\n",
    "\n",
    "<p>在从 <code>1</code> 到 <code>n</code> 的每个步骤 <code>i</code> 中（假设二进制字符串和 <code>arr</code> 都是从 <code>1</code> 开始索引的情况下），二进制字符串上位于位置 <code>arr[i]</code> 的位将会设为 <code>1</code> 。</p>\n",
    "\n",
    "<p>给你一个整数 <code>m</code> ，请你找出二进制字符串上存在长度为 <code>m</code> 的一组 <code>1</code> 的最后步骤。一组 <code>1</code> 是一个连续的、由 <code>1</code> 组成的子串，且左右两边不再有可以延伸的 <code>1</code> 。</p>\n",
    "\n",
    "<p>返回存在长度 <strong>恰好</strong> 为 <code>m</code> 的 <strong>一组 <code>1</code>&nbsp;</strong> 的最后步骤。如果不存在这样的步骤，请返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [3,5,1,2,4], m = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：\n",
    "</strong>步骤 1：&quot;00<strong>1</strong>00&quot;，由 1 构成的组：[&quot;1&quot;]\n",
    "步骤 2：&quot;0010<strong>1</strong>&quot;，由 1 构成的组：[&quot;1&quot;, &quot;1&quot;]\n",
    "步骤 3：&quot;<strong>1</strong>0101&quot;，由 1 构成的组：[&quot;1&quot;, &quot;1&quot;, &quot;1&quot;]\n",
    "步骤 4：&quot;1<strong>1</strong>101&quot;，由 1 构成的组：[&quot;111&quot;, &quot;1&quot;]\n",
    "步骤 5：&quot;111<strong>1</strong>1&quot;，由 1 构成的组：[&quot;11111&quot;]\n",
    "存在长度为 1 的一组 1 的最后步骤是步骤 4 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [3,1,5,4,2], m = 2\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：\n",
    "</strong>步骤 1：&quot;00<strong>1</strong>00&quot;，由 1 构成的组：[&quot;1&quot;]\n",
    "步骤 2：&quot;<strong>1</strong>0100&quot;，由 1 构成的组：[&quot;1&quot;, &quot;1&quot;]\n",
    "步骤 3：&quot;1010<strong>1</strong>&quot;，由 1 构成的组：[&quot;1&quot;, &quot;1&quot;, &quot;1&quot;]\n",
    "步骤 4：&quot;101<strong>1</strong>1&quot;，由 1 构成的组：[&quot;1&quot;, &quot;111&quot;]\n",
    "步骤 5：&quot;1<strong>1</strong>111&quot;，由 1 构成的组：[&quot;11111&quot;]\n",
    "不管是哪一步骤都无法形成长度为 2 的一组 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1], m = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,1], m = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == arr.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= n</code></li>\n",
    "\t<li><code>arr</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "\t<li><code>1 &lt;= m&nbsp;&lt;= arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-latest-group-of-size-m](https://leetcode.cn/problems/find-latest-group-of-size-m/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-latest-group-of-size-m](https://leetcode.cn/problems/find-latest-group-of-size-m/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,1,2,4]\\n1', '[3,1,5,4,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[1,n]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i]\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if l <=p<=r:\n",
    "                if p-l == m or r-p==m:\n",
    "                    return i\n",
    "                seqs.pop(j)\n",
    "                if r-p>m:\n",
    "                    seqs.insert(j, [p+1,r])\n",
    "                if p-l>m:\n",
    "                    seqs.insert(j, [l,p-1])\n",
    "                if not seqs:\n",
    "                    break\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        # n = len(arr)\n",
    "        # if m == n:\n",
    "        #     return n\n",
    "\n",
    "        # lens = [0] * (n+2)\n",
    "        # cnt = 0\n",
    "        # ans = -2\n",
    "        # for i, p in enumerate(arr):\n",
    "        #     ll,rl = lens[p-1], lens[p+1]\n",
    "        #     l = ll + rl + 1\n",
    "        #     lens[p-ll] = lens[p+rl] = l \n",
    "        #     if l == m:\n",
    "        #         ans = i \n",
    "        # return ans+1\n",
    "\n",
    "\n",
    "        n = len(arr)\n",
    "        if m == n: return n\n",
    "        lth = [0]*(n+2)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            x = arr[i]\n",
    "            left = lth[x-1]\n",
    "            right = lth[x+1]\n",
    "            if left == m or right == m:\n",
    "                ans = i\n",
    "            lth[x-left] = left + right + 1\n",
    "            lth[x+right] = left + right + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int: \n",
    "        n = len(arr)\n",
    "        L = [0] * (n + 2)\n",
    "        cnt, ans = 0, -1\n",
    "        for i, x in enumerate(arr):\n",
    "            l = L[x - 1] if L[x - 1] else x\n",
    "            r = L[x + 1] if L[x + 1] else x\n",
    "            # 合并 \n",
    "            if x - l == m : cnt -= 1\n",
    "            if r - x == m : cnt -= 1\n",
    "            if r - l + 1 == m : cnt += 1\n",
    "            if cnt : ans = i + 1\n",
    "            L[l] = r\n",
    "            L[r] = l \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: list[int], m: int) -> int:\n",
    "        continue_seq = []\n",
    "        continue_seq.append([1, len(arr)])\n",
    "        if m == len(arr):\n",
    "            return len(arr)\n",
    "        for index in range(len(arr)-1, -1, -1):\n",
    "            for seq in continue_seq:\n",
    "                if seq[0] <= arr[index] <= seq[1]:\n",
    "                    if arr[index] - seq[0] == m or seq[1] - arr[index] == m:\n",
    "                        return index\n",
    "                    if arr[index] - seq[0] > m:\n",
    "                        continue_seq.append([seq[0], arr[index]-1])\n",
    "                    if seq[1] - arr[index] > m:\n",
    "                        continue_seq.append([arr[index]+1, seq[1]])\n",
    "                    continue_seq.remove(seq)\n",
    "                    break\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[1,n]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i]\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if l <=p<=r:\n",
    "                if p-l == m or r-p==m:\n",
    "                    return i\n",
    "                seqs.pop(j)\n",
    "                if r-p>m:\n",
    "                    seqs.insert(j, [p+1,r])\n",
    "                if p-l>m:\n",
    "                    seqs.insert(j, [l,p-1])\n",
    "                if not seqs:\n",
    "                    break\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        lens = [0] * (n+2)\n",
    "        cnt = 0\n",
    "        ans = -1\n",
    "        for i, p in enumerate(arr):\n",
    "            ll,rl = lens[p-1], lens[p+1]\n",
    "            if ll == m or rl == m:\n",
    "                ans = i\n",
    "            l = ll + rl + 1\n",
    "            lens[p-ll] = lens[p+rl] = l \n",
    "        return ans\n",
    "\n",
    "\n",
    "        # n = len(arr)\n",
    "        # if m == n: return n\n",
    "        # lth = [0]*(n+2)\n",
    "        # ans = -1\n",
    "        # for i in range(n):\n",
    "        #     x = arr[i]\n",
    "        #     left = lth[x-1]\n",
    "        #     right = lth[x+1]\n",
    "        #     if left == m or right == m:\n",
    "        #         ans = i\n",
    "        #     lth[x-left] = left + right + 1\n",
    "        #     lth[x+right] = left + right + 1\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[1,n]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i]\n",
    "            for j, [l,r] in enumerate(seqs):\n",
    "                if l <= p <= r:\n",
    "                    if p-l == m or r-p == m:\n",
    "                        return i\n",
    "                    if p - l > m:\n",
    "                        seqs.append([l,p-1])\n",
    "                    if r - p > m:\n",
    "                        seqs.append([p+1,r])\n",
    "                    seqs.pop(j)\n",
    "                    break\n",
    "            \n",
    "        return -1\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findLatestStep(self, arr: list[int], m: int) -> int:\n",
    "#         continue_seq = []\n",
    "#         continue_seq.append([1, len(arr)])\n",
    "#         if m == len(arr):\n",
    "#             return len(arr)\n",
    "#         for index in range(len(arr)-1, -1, -1):\n",
    "#             for seq in continue_seq:\n",
    "#                 if seq[0] <= arr[index] <= seq[1]:\n",
    "#                     if arr[index] - seq[0] == m or seq[1] - arr[index] == m:\n",
    "#                         return index\n",
    "#                     if arr[index] - seq[0] > m:\n",
    "#                         continue_seq.append([seq[0], arr[index]-1])\n",
    "#                     if seq[1] - arr[index] > m:\n",
    "#                         continue_seq.append([arr[index]+1, seq[1]])\n",
    "#                     continue_seq.remove(seq)\n",
    "#                     break\n",
    "#         return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        if m==len(arr):\n",
    "            return m\n",
    "        l=[0,len(arr)+1]\n",
    "        for i,t in enumerate(arr[::-1]):\n",
    "            idx=bisect.bisect(l,t)\n",
    "            l.insert(idx,t)\n",
    "            if l[idx+1]-l[idx]-1==m or l[idx]-l[idx-1]-1==m:#此即为这次更新的位置左右连续1的个数， 已经考察过的位置就不用再看了，必定不符合条件\n",
    "                return len(arr)-i-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect\n",
    "class Solution:\n",
    "    def findLatestStep(self, nums, m: int) -> int:\n",
    "\n",
    "        # M1\n",
    "        n = len(nums)\n",
    "        if n == m: return m\n",
    "        l = [0, n + 1]\n",
    "        for i, v in enumerate(nums[::-1], 1):\n",
    "            idx = bisect(l, v)\n",
    "            if m + 1 in [v - l[idx - 1], l[idx] - v]: return n - i\n",
    "            l.insert(idx, v)\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[0,n-1]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i] - 1\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if l == r == p:\n",
    "                seqs[j:j+1] = []\n",
    "                # continue\n",
    "            elif p == l:\n",
    "                seqs[j][0] = l+1\n",
    "            elif p == r:\n",
    "                seqs[j][1] = r-1\n",
    "            else:\n",
    "                seqs[j:j+1] = [[l,p-1],[p+1,r]]\n",
    "            if p-l == m or r-p == m:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[0,n-1]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i] - 1\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            # if l == r == p:\n",
    "            #     seqs.pop(j)\n",
    "            #     continue\n",
    "            if p == l:\n",
    "                seqs[j][0] = l+1\n",
    "            elif p == r:\n",
    "                seqs[j][1] = r-1\n",
    "            else:\n",
    "                seqs[j:j+1] = [[l,p-1],[p+1,r]]\n",
    "            if p-l == m or r-p == m:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[0,n-1]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i] - 1\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if p == l:\n",
    "                seqs[j][0] = l+1\n",
    "            elif p == r:\n",
    "                seqs[j][1] = r-1\n",
    "            else:\n",
    "                seqs[j:j+1] = [[l,p-1],[p+1,r]]\n",
    "            if p-l == m or r-p == m:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[0,n-1]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i] - 1\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if l == r == p:\n",
    "                seqs.pop(j)\n",
    "                continue\n",
    "            if p == l:\n",
    "                seqs[j][0] = l+1\n",
    "            elif p == r:\n",
    "                seqs[j][1] = r-1\n",
    "            else:\n",
    "                seqs[j:j+1] = [[l,p-1],[p+1,r]]\n",
    "            if p-l == m or r-p == m:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "        intervals = SortedList()\n",
    "        intervals.add((1, n))\n",
    "        arr.reverse()\n",
    "        for i, p in enumerate(arr):\n",
    "            j = bisect_left(intervals, p, key=lambda x: x[1])\n",
    "            t = intervals[j]\n",
    "            if p - t[0] == m:\n",
    "                return n - i - 1\n",
    "            if t[1] - p == m:\n",
    "                return n - i - 1\n",
    "            intervals.remove(t)\n",
    "            if p - 1 >= t[0]:\n",
    "                intervals.add((t[0], p - 1))\n",
    "            if p + 1 <= t[1]:\n",
    "                intervals.add((p + 1, t[1]))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[0,n-1]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i] - 1\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if l == r == p:\n",
    "                seqs.pop(j)\n",
    "                continue\n",
    "            if p == l:\n",
    "                seqs[j][0] = l+1\n",
    "            elif p == r:\n",
    "                seqs[j][1] = r-1\n",
    "            else:\n",
    "                seqs[j:j+1] = [[l,p-1],[p+1,r]]\n",
    "            if p-l == m or r-p == m:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[0,n-1]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i] - 1\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if l == r == p:\n",
    "                seqs.pop(j)\n",
    "                continue\n",
    "            if p == l:\n",
    "                seqs[j][0] = l+1\n",
    "            elif p == r:\n",
    "                seqs[j][1] = r-1\n",
    "            else:\n",
    "                seqs[j:j+1] = [[l,p-1],[p+1,r]]\n",
    "            if p-l == m or r-p == m:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        if m == n:\n",
    "            return n\n",
    "\n",
    "        seqs = [[0,n-1]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p = arr[i] - 1\n",
    "            j = bisect.bisect(seqs, [p,n])-1\n",
    "            l,r = seqs[j]\n",
    "            if l == r == p:\n",
    "                seqs.pop(j)\n",
    "                # continue\n",
    "            elif p == l:\n",
    "                seqs[j][0] = l+1\n",
    "            elif p == r:\n",
    "                seqs[j][1] = r-1\n",
    "            else:\n",
    "                seqs[j:j+1] = [[l,p-1],[p+1,r]]\n",
    "            if p-l == m or r-p == m:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        # O(nlogn)\n",
    "        n = len(arr)\n",
    "        if n == m: return n\n",
    "        leaves = SortedList([(1, n)])\n",
    "        print(leaves)\n",
    "        for k, i in enumerate(arr[:0:-1]):\n",
    "            # print(k, n)\n",
    "            pos = bisect_left(leaves, i, key=lambda x: x[1])\n",
    "            # print(leaves, pos, i)\n",
    "            if pos >= len(leaves): \n",
    "                break\n",
    "            # pos = leaves.bisect_left(i)\n",
    "            l, r = leaves[pos]\n",
    "            leaves.remove((l, r))\n",
    "            if i - l == m or r - i == m: return n - k - 1\n",
    "            if l <= i - 1: leaves.add((l, i - 1))\n",
    "            if r >= i + 1: leaves.add((i + 1, r))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        # O(nlogn)\n",
    "        n = len(arr)\n",
    "        if n == m: return n\n",
    "        leaves = SortedList([(1, n)])\n",
    "        for k, i in enumerate(arr[:0:-1]):\n",
    "            pos = bisect_left(leaves, i, key=lambda x: x[1])\n",
    "            l, r = leaves[pos]\n",
    "            leaves.remove((l, r))\n",
    "            if i - l == m or r - i == m: return n - k - 1\n",
    "            if l <= i - 1: leaves.add((l, i - 1))\n",
    "            if r >= i + 1: leaves.add((i + 1, r))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        endpoints = [(-1, -1) for _ in range(n + 1)]\n",
    "        cnt = 0\n",
    "        ret = -1\n",
    "\n",
    "        for i in range(n):\n",
    "            left = right = arr[i]\n",
    "            if arr[i] > 1 and endpoints[arr[i] - 1][0] != -1:\n",
    "                left = endpoints[arr[i] - 1][0]\n",
    "                leftLength = endpoints[arr[i] - 1][1] - endpoints[arr[i] - 1][0] + 1\n",
    "                if leftLength == m:\n",
    "                    cnt -= 1\n",
    "            if arr[i] < n and endpoints[arr[i] + 1][1] != -1:\n",
    "                right = endpoints[arr[i] + 1][1]\n",
    "                rightLength = endpoints[arr[i] + 1][1] - endpoints[arr[i] + 1][0] + 1\n",
    "                if rightLength == m:\n",
    "                    cnt -= 1\n",
    "            \n",
    "            length = right - left + 1\n",
    "            if length == m:\n",
    "                cnt += 1\n",
    "            if cnt > 0:\n",
    "                ret = i + 1\n",
    "            endpoints[left] = endpoints[right] = (left, right)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    ## 时间复杂度为 O(n), 对相邻的集合进行合并\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        if m == len(arr):\n",
    "            return m\n",
    "        ### 从后往前检索, 每次合并连续的\n",
    "        nums = [(-1, -1)] * (len(arr)+1)\n",
    "        count, res = 0, -1\n",
    "        for i in range(len(arr)):\n",
    "            left_1, right_2 = arr[i], arr[i]\n",
    "            ## 左边处理\n",
    "            if nums[arr[i]-1][0] != -1:\n",
    "                left_1, left_2 = nums[arr[i]-1][0], nums[arr[i]-1][1]\n",
    "                if left_2 - left_1 + 1 == m:\n",
    "                    count -= 1\n",
    "\n",
    "            ## 右边\n",
    "            if arr[i] < len(arr) and nums[arr[i]+1][0] != -1:\n",
    "                right_1, right_2 = nums[arr[i]+1][0], nums[arr[i]+1][1]\n",
    "                if right_2 - right_1 + 1 == m:\n",
    "                    count -= 1\n",
    "            ## 更新nums 中组中的 最左边和最右边的 index\n",
    "            ## 因为 [left_1, right_2] 属于同一个分组了, 后续遍历不会访问到其中间的 index, 中间 index 对应的 nums 不用修改\n",
    "            group_len = right_2 - left_1 + 1\n",
    "            if group_len == m:\n",
    "                count += 1\n",
    "            if count > 0:\n",
    "                res = i+1\n",
    "            nums[left_1] = (left_1, right_2)\n",
    "            nums[right_2] = (left_1, right_2)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        # def _is(s):\n",
    "        #     lst = s.split(\"0\")\n",
    "        #     if \"1\" * m in lst:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False \n",
    "        # def tranform(k):\n",
    "        #     lst = list(cur)\n",
    "\n",
    "        #     for i in range(k + 1):\n",
    "        #         lst[i] = \"1\"\n",
    "        #     return \"\".join(lst)\n",
    "                \n",
    "        # res = -1\n",
    "        # n = len(arr)\n",
    "        # cur = \"0\" * n\n",
    "        # left = 0\n",
    "        # right = n-1\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "        #     if _is(tranform(mid)):\n",
    "        #         res = max(res, mid + 1)\n",
    "        #         right = mid -1\n",
    "\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "        # return res\n",
    "        n = len(arr)\n",
    "        endpoints = [(-1, -1) for _ in range(n+1)]\n",
    "        cnt = 0\n",
    "        res = -1\n",
    "\n",
    "        for i in range(n):\n",
    "            left = right = arr[i]\n",
    "            if arr[i] > 1 and endpoints[arr[i]-1][0] != -1:\n",
    "                left = endpoints[arr[i]-1][0]\n",
    "                left_length = endpoints[arr[i]-1][1] - endpoints[arr[i]-1][0] + 1\n",
    "                if left_length == m:\n",
    "                    cnt -= 1\n",
    "            if arr[i] < n and endpoints[arr[i]+1][1] != -1:\n",
    "                right = endpoints[arr[i]+1][1]\n",
    "                right_length = endpoints[arr[i]+1][1] - endpoints[arr[i]+1][0] + 1\n",
    "                if right_length == m :\n",
    "                    cnt -= 1\n",
    "            length = right - left + 1\n",
    "            if length == m:\n",
    "                cnt += 1\n",
    "            if cnt > 0:\n",
    "                res = i + 1\n",
    "            endpoints[left] = endpoints[right] = (left, right)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 模拟\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        endpoints = [(-1, -1) for _ in range(n + 1)]\n",
    "        cnt = 0\n",
    "        ret = -1\n",
    "\n",
    "        for i in range(n):\n",
    "            left = right = arr[i]\n",
    "            if arr[i] > 1 and endpoints[arr[i] - 1][0] != -1:\n",
    "                left = endpoints[arr[i] - 1][0]\n",
    "                leftLength = endpoints[arr[i] - 1][1] - endpoints[arr[i] - 1][0] + 1;\n",
    "                if leftLength == m:\n",
    "                    cnt -= 1\n",
    "            if arr[i] < n and endpoints[arr[i] + 1][1] != -1:\n",
    "                right = endpoints[arr[i] + 1][1]\n",
    "                rightLength = endpoints[arr[i] + 1][1] - endpoints[arr[i] + 1][0] + 1;\n",
    "                if rightLength == m:\n",
    "                    cnt -= 1\n",
    "            \n",
    "            length = right - left + 1\n",
    "            if length == m:\n",
    "                cnt += 1\n",
    "            if cnt > 0:\n",
    "                ret = i + 1\n",
    "            endpoints[left] = endpoints[right] = (left, right)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        endpoints = [(-1, -1) for _ in range(n + 1)]\n",
    "        cnt = 0\n",
    "        ret = -1\n",
    "\n",
    "        for i in range(n):\n",
    "            left = right = arr[i]\n",
    "            if arr[i] > 1 and endpoints[arr[i] - 1][0] != -1:\n",
    "                left = endpoints[arr[i] - 1][0]\n",
    "                leftLength = endpoints[arr[i] - 1][1] - endpoints[arr[i] - 1][0] + 1;\n",
    "                if leftLength == m:\n",
    "                    cnt -= 1\n",
    "            if arr[i] < n and endpoints[arr[i] + 1][1] != -1:\n",
    "                right = endpoints[arr[i] + 1][1]\n",
    "                rightLength = endpoints[arr[i] + 1][1] - endpoints[arr[i] + 1][0] + 1;\n",
    "                if rightLength == m:\n",
    "                    cnt -= 1\n",
    "            \n",
    "            length = right - left + 1\n",
    "            if length == m:\n",
    "                cnt += 1\n",
    "            if cnt > 0:\n",
    "                ret = i + 1\n",
    "            endpoints[left] = endpoints[right] = (left, right)\n",
    "\n",
    "        return ret\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/find-latest-group-of-size-m/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        endpoint = []\n",
    "        res = -1\n",
    "        count_m = 0\n",
    "        for i in range(len(arr)+1):\n",
    "            endpoint.append([-1,-1])\n",
    "        for i in range(len(arr)) :\n",
    "            left = arr[i]\n",
    "            right = arr[i]\n",
    "    \n",
    "            if arr[i]-1>0 and endpoint[arr[i]-1][1] != -1:\n",
    "                if endpoint[endpoint[arr[i]-1][0]][1]-endpoint[endpoint[arr[i]-1][0]][0]+1==m:\n",
    "                    count_m-=1\n",
    "                left = endpoint[endpoint[arr[i]-1][0]][0]\n",
    "            if arr[i]+1<=len(arr) and endpoint[arr[i]+1][0] != -1:\n",
    "                if endpoint[endpoint[arr[i]+1][1]][1]-endpoint[endpoint[arr[i]+1][1]][0]+1==m:\n",
    "                    count_m-=1\n",
    "                right = endpoint[endpoint[arr[i]+1][1]][1]\n",
    "            if right-left+1==m:\n",
    "                count_m+=1\n",
    "            if count_m>0:\n",
    "                res = i+1\n",
    "            endpoint[left] = [left,right]\n",
    "            endpoint[right] = [left,right]\n",
    "        return res\n",
    "            \n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        x = [0] * (n+2)\n",
    "        c = Counter()\n",
    "        ans = -1\n",
    "        for step,i in enumerate(arr, start=1):\n",
    "            l, r = x[i-1], x[i+1]\n",
    "            x[i] = i\n",
    "            if l == r == 0:\n",
    "                c[1] += 1\n",
    "            elif l == 0:\n",
    "                x[i] = r\n",
    "                x[r] = i\n",
    "                c[r-i] -= 1\n",
    "                c[r-i+1] += 1\n",
    "            elif r == 0:\n",
    "                x[i] = l\n",
    "                x[l] = i\n",
    "                c[i-l] -= 1\n",
    "                c[i-l+1] += 1\n",
    "            else:\n",
    "                x[l] = r\n",
    "                x[r] = l\n",
    "                c[r-i] -= 1\n",
    "                c[i-l] -= 1\n",
    "                c[r-l+1] += 1\n",
    "            if c[m]:\n",
    "                ans = step\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        pos = [[-1,-1] for _ in range(n)]\n",
    "        bit = 0\n",
    "        mapping = {}\n",
    "        result = -1\n",
    "        for k,a in enumerate(arr):\n",
    "            i = a - 1\n",
    "            bit |= (1 << i)\n",
    "            if(i-1>=0 and bit&(1<<(i-1))>0 and i+1<=n-1 and bit&(1<<(i+1))>0):\n",
    "                l1,r1 = pos[i-1]\n",
    "                l2,r2 = pos[i+1]\n",
    "                pos[l1] = [l1,r2]\n",
    "                pos[r2] = [l1,r2]\n",
    "                mapping[r1-l1+1] -= 1\n",
    "                if(mapping[r1-l1+1] == 0):\n",
    "                    del mapping[r1-l1+1]\n",
    "                mapping[r2-l2+1] -= 1\n",
    "                if(mapping[r2-l2+1] == 0):\n",
    "                    del mapping[r2-l2+1]\n",
    "                if(r2-l1+1 not in mapping):\n",
    "                    mapping[r2-l1+1] = 1\n",
    "                else:\n",
    "                    mapping[r2-l1+1] += 1\n",
    "            elif(i-1>=0 and bit&(1<<(i-1))>0):\n",
    "                l1,r1 = pos[i-1]\n",
    "                pos[i] = [l1,i]\n",
    "                pos[l1] = [l1,i]\n",
    "                mapping[r1-l1+1] -= 1\n",
    "                if(mapping[r1-l1+1] == 0):\n",
    "                    del mapping[r1-l1+1]\n",
    "                if(i-l1+1 not in mapping):\n",
    "                    mapping[i-l1+1] = 1\n",
    "                else:\n",
    "                    mapping[i-l1+1] += 1\n",
    "            elif(i+1<=n-1 and bit&(1<<(i+1))>0):\n",
    "                l2,r2 = pos[i+1]\n",
    "                pos[i] = [i,r2]\n",
    "                pos[r2] = [i,r2]\n",
    "\n",
    "                mapping[r2-l2+1] -= 1\n",
    "                if(mapping[r2-l2+1] == 0):\n",
    "                    del mapping[r2-l2+1]\n",
    "                if(r2-i+1 not in mapping):\n",
    "                    mapping[r2-i+1] = 1\n",
    "                else:\n",
    "                    mapping[r2-i+1] += 1\n",
    "            else:\n",
    "                pos[i] = [i,i]\n",
    "                if(1 not in mapping):\n",
    "                    mapping[1] = 1\n",
    "                else:\n",
    "                    mapping[1] += 1\n",
    "            if(m in mapping):\n",
    "                result = k + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        pos = [[-1,-1] for _ in range(n)]\n",
    "        bit = 0\n",
    "        mapping = {}\n",
    "        result = -1\n",
    "        for k,a in enumerate(arr):\n",
    "            i = a - 1\n",
    "            bit |= (1 << i)\n",
    "            if(i-1>=0 and bit&(1<<(i-1))>0 and i+1<=n-1 and bit&(1<<(i+1))>0):\n",
    "                l1,r1 = pos[i-1]\n",
    "                l2,r2 = pos[i+1]\n",
    "                pos[l1] = [l1,r2]\n",
    "                pos[r2] = [l1,r2]\n",
    "                mapping[r1-l1+1] -= 1\n",
    "                if(mapping[r1-l1+1] == 0):\n",
    "                    del mapping[r1-l1+1]\n",
    "                mapping[r2-l2+1] -= 1\n",
    "                if(mapping[r2-l2+1] == 0):\n",
    "                    del mapping[r2-l2+1]\n",
    "                if(r2-l1+1 not in mapping):\n",
    "                    mapping[r2-l1+1] = 1\n",
    "                else:\n",
    "                    mapping[r2-l1+1] += 1\n",
    "            elif(i-1>=0 and bit&(1<<(i-1))>0):\n",
    "                l1,r1 = pos[i-1]\n",
    "                pos[i] = [l1,i]\n",
    "                pos[l1] = [l1,i]\n",
    "                mapping[r1-l1+1] -= 1\n",
    "                if(mapping[r1-l1+1] == 0):\n",
    "                    del mapping[r1-l1+1]\n",
    "                if(i-l1+1 not in mapping):\n",
    "                    mapping[i-l1+1] = 1\n",
    "                else:\n",
    "                    mapping[i-l1+1] += 1\n",
    "            elif(i+1<=n-1 and bit&(1<<(i+1))>0):\n",
    "                l2,r2 = pos[i+1]\n",
    "                pos[i] = [i,r2]\n",
    "                pos[r2] = [i,r2]\n",
    "\n",
    "                mapping[r2-l2+1] -= 1\n",
    "                if(mapping[r2-l2+1] == 0):\n",
    "                    del mapping[r2-l2+1]\n",
    "                if(r2-i+1 not in mapping):\n",
    "                    mapping[r2-i+1] = 1\n",
    "                else:\n",
    "                    mapping[r2-i+1] += 1\n",
    "            else:\n",
    "                pos[i] = [i,i]\n",
    "                if(1 not in mapping):\n",
    "                    mapping[1] = 1\n",
    "                else:\n",
    "                    mapping[1] += 1\n",
    "            if(m in mapping):\n",
    "                result = k + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        uf = UnionFind(n)\n",
    "        ans = -1\n",
    "        lst = [0]*n\n",
    "        dct = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            x = arr[i]-1\n",
    "            if x-1>=0 and lst[x-1]:\n",
    "                dct[uf.size[uf.find(x-1)]] -= 1\n",
    "                uf.union(x-1, x)\n",
    "            if x+1<n and lst[x+1]:\n",
    "                dct[uf.size[uf.find(x + 1)]] -= 1\n",
    "                uf.union(x+1, x)\n",
    "            lst[x] = 1\n",
    "            dct[uf.size[uf.find(x)]] += 1\n",
    "            if dct[m]:\n",
    "                ans = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        def find(x):\n",
    "            if f[x] != x: f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            x, y = find(x), find(y)\n",
    "            f[x] = y\n",
    "            sz[y] += sz[x]\n",
    "\n",
    "        n = len(arr)\n",
    "        f = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "\n",
    "        cnt = defaultdict(int)\n",
    "        ans = -1\n",
    "\n",
    "        for i, x in enumerate(arr):\n",
    "            sz[x] = 1\n",
    "            if x - 1 >= 1 and (old_sz1 := sz[find(x - 1)]):\n",
    "                union(x, x - 1)\n",
    "                cnt[old_sz1] -= 1\n",
    "            if x + 1 <= n and (old_sz2 := sz[find(x + 1)]):\n",
    "                union(x, x + 1)\n",
    "                cnt[old_sz2] -= 1\n",
    "            new_sz = sz[find(x)]\n",
    "            cnt[new_sz] += 1\n",
    "            if cnt[m] > 0:\n",
    "                ans = i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr) \n",
    "        vis = [0] *(n+1)\n",
    "        cnt = collections.Counter()\n",
    "        ans = -1 \n",
    "        data = [i for i in range(n+1)] \n",
    "        rank = [1] * (n+1)\n",
    "        def find(x):\n",
    "            if x == data[x]:\n",
    "                return x\n",
    "            else:\n",
    "                data[x] = find(data[x]) \n",
    "                return data[x] \n",
    "        def un(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx == fy:\n",
    "                return False \n",
    "            else:\n",
    "                data[fy] =fx \n",
    "                rank[fx] += rank[fy]\n",
    "                return True \n",
    "                \n",
    "        for i in range(n):\n",
    "            if not vis[arr[i]]:\n",
    "                vis[arr[i]] = 1\n",
    "                if arr[i] - 1 >= 1 and vis[arr[i]-1]:\n",
    "                    fx = find(arr[i]-1)\n",
    "                    cnt[rank[fx]] -= 1\n",
    "                    un(arr[i]- 1,arr[i])\n",
    "                if arr[i] + 1 <= n and vis[arr[i]+1]:\n",
    "                    fx = find(arr[i]+1)\n",
    "                    cnt[rank[fx]] -= 1\n",
    "                    un(arr[i], arr[i]+1)\n",
    "                fx = find(arr[i]) \n",
    "                cnt[rank[fx]] += 1\n",
    "\n",
    "            if cnt[m] > 0:\n",
    "                ans = i+1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        fa = list(range(n + 1))\n",
    "        sum = [0] * (n + 1)\n",
    "        ans = -1\n",
    "        cnt = 0\n",
    "        def find(x : int) ->int :\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for i in range(n) :\n",
    "            x = arr[i] - 1\n",
    "            to = find(x + 1)\n",
    "            fa[x] = to\n",
    "            if sum[x] == m:\n",
    "                cnt -= 1\n",
    "            if sum[to] == m:\n",
    "                cnt -= 1\n",
    "            #print(\"1\", sum[to], sum[x], x, to)\n",
    "            sum[to] += sum[x] + 1\n",
    "            if sum[to] == m:\n",
    "                cnt += 1\n",
    "            #print(\"2\", sum[to], sum[x], x, to)\n",
    "            if cnt > 0:\n",
    "                ans = i + 1\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\r\n",
    "        # 并查集 \r\n",
    "        # 将 1 相邻的 1 下标集合合并 \r\n",
    "        # 某一步集操作 \r\n",
    "        # 用 map 维护长为m 的 子串开头 \r\n",
    "        # 合并操作的同时 维护map\r\n",
    "\r\n",
    "        n = len(arr)\r\n",
    "        s = list(range(n + 1))\r\n",
    "        size = [0] * (n + 1)\r\n",
    "        def find(x: int) -> int:\r\n",
    "            if x != s[x]:\r\n",
    "                s[x] = find(s[x])\r\n",
    "            return s[x] \r\n",
    "\r\n",
    "        def union(x: int, y: int):\r\n",
    "            sx = find(x)\r\n",
    "            sy = find(y) \r\n",
    "            if sx != sy:\r\n",
    "                s[sx] = sy \r\n",
    "                size[sy] += size[sx]\r\n",
    "                size[sx] = size[sy]\r\n",
    "            return size[sx]\r\n",
    "        res = -1 \r\n",
    "        mp = set()\r\n",
    "        for i, x in enumerate(arr, 1):\r\n",
    "            size[x] = 1\r\n",
    "            if x - 1 >= 1 and size[x - 1]:\r\n",
    "                if size[find(x - 1)] == m:\r\n",
    "                    mp.remove(find(x - 1))\r\n",
    "                union(x - 1, x)\r\n",
    "            if x + 1 <= n and size[x + 1]:\r\n",
    "                if size[find(x + 1)] == m:\r\n",
    "                    mp.remove(find(x + 1))\r\n",
    "                union(x, x + 1)\r\n",
    "            sz = size[find(x)]\r\n",
    "            if sz == m:\r\n",
    "                mp.add(find(x))\r\n",
    "            if len(mp):\r\n",
    "                res = i \r\n",
    "        return res \r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, m):\n",
    "        self.arr = set()\n",
    "        self.father = {}\n",
    "        self.root_depth = {}\n",
    "        self.m = m\n",
    "        self.cnt = 0\n",
    "    def add(self, val):\n",
    "        self.arr.add(val)\n",
    "        self.father[val] = val\n",
    "        self.root_depth[val] = 1\n",
    "        if self.m == 1:\n",
    "            self.cnt += 1\n",
    "\n",
    "\n",
    "    def find(self, val):\n",
    "        val_father = self.father.get(val, None)\n",
    "        if not val_father:\n",
    "            return None\n",
    "        if val_father == val:\n",
    "            return val\n",
    "        else:\n",
    "            return self.find(val_father)\n",
    "\n",
    "    def merge(self, val1, val2):\n",
    "        val1_father = self.find(val1)\n",
    "        val2_father = self.find(val2)\n",
    "        if val1_father < val2_father:\n",
    "            self.father[val2_father] = val1_father\n",
    "            if self.root_depth[val1_father] == self.m:\n",
    "                self.cnt -= 1\n",
    "            if self.root_depth[val2_father] == self.m:\n",
    "                self.cnt -= 1\n",
    "            self.root_depth[val1_father] += self.root_depth[val2_father]\n",
    "            if self.root_depth[val1_father] == self.m:\n",
    "                self.cnt += 1\n",
    "            self.root_depth.pop(val2_father)\n",
    "            return val1_father\n",
    "        else:\n",
    "            self.father[val1_father] = val2_father\n",
    "            if self.root_depth[val1_father] == self.m:\n",
    "                self.cnt -= 1\n",
    "            if self.root_depth[val2_father] == self.m:\n",
    "                self.cnt -= 1\n",
    "            self.root_depth[val2_father] += self.root_depth[val1_father]\n",
    "            if self.root_depth[val2_father] == self.m:\n",
    "                self.cnt += 1\n",
    "            self.root_depth.pop(val1_father)\n",
    "            return val2_father\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        uf = UnionFindSet(m)\n",
    "        step = -1\n",
    "        for i in range(len(arr)):\n",
    "            uf.add(arr[i])\n",
    "            f_1 = True if arr[i] - 1 in uf.arr else False\n",
    "            f_2 = True if arr[i] + 1 in uf.arr else False\n",
    "            if f_2:\n",
    "                uf.merge(arr[i], arr[i] + 1)\n",
    "            if f_1:\n",
    "                uf.merge(arr[i], arr[i] - 1)\n",
    "            if uf.cnt > 0:\n",
    "                step = i + 1\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLatestStep(self, arr: List[int], m: int) -> int:\n",
    "        n = len(arr)\n",
    "        pos = [[-1,-1] for _ in range(n)]\n",
    "        bit = 0\n",
    "        mapping = {}\n",
    "        result = -1\n",
    "        for k,a in enumerate(arr):\n",
    "            i = a - 1\n",
    "            bit |= (1 << i)\n",
    "            if(i-1>=0 and bit&(1<<(i-1))>0 and i+1<=n-1 and bit&(1<<(i+1))>0):\n",
    "                l1,r1 = pos[i-1]\n",
    "                l2,r2 = pos[i+1]\n",
    "                pos[l1] = [l1,r2]\n",
    "                pos[r2] = [l1,r2]\n",
    "                mapping[r1-l1+1] -= 1\n",
    "                # if(mapping[r1-l1+1] == 0):\n",
    "                #     del mapping[r1-l1+1]\n",
    "                mapping[r2-l2+1] -= 1\n",
    "                # if(mapping[r2-l2+1] == 0):\n",
    "                #     del mapping[r2-l2+1]\n",
    "                if(r2-l1+1 not in mapping):\n",
    "                    mapping[r2-l1+1] = 1\n",
    "                else:\n",
    "                    mapping[r2-l1+1] += 1\n",
    "            elif(i-1>=0 and bit&(1<<(i-1))>0):\n",
    "                l1,r1 = pos[i-1]\n",
    "                pos[i] = [l1,i]\n",
    "                pos[l1] = [l1,i]\n",
    "                mapping[r1-l1+1] -= 1\n",
    "                # if(mapping[r1-l1+1] == 0):\n",
    "                #     del mapping[r1-l1+1]\n",
    "                if(i-l1+1 not in mapping):\n",
    "                    mapping[i-l1+1] = 1\n",
    "                else:\n",
    "                    mapping[i-l1+1] += 1\n",
    "            elif(i+1<=n-1 and bit&(1<<(i+1))>0):\n",
    "                l2,r2 = pos[i+1]\n",
    "                pos[i] = [i,r2]\n",
    "                pos[r2] = [i,r2]\n",
    "\n",
    "                mapping[r2-l2+1] -= 1\n",
    "                # if(mapping[r2-l2+1] == 0):\n",
    "                #     del mapping[r2-l2+1]\n",
    "                if(r2-i+1 not in mapping):\n",
    "                    mapping[r2-i+1] = 1\n",
    "                else:\n",
    "                    mapping[r2-i+1] += 1\n",
    "            else:\n",
    "                pos[i] = [i,i]\n",
    "                if(1 not in mapping):\n",
    "                    mapping[1] = 1\n",
    "                else:\n",
    "                    mapping[1] += 1\n",
    "            if(m in mapping and mapping[m] > 0):\n",
    "                result = k + 1\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
